


#include <iostream>
#include <string>
#include <stack>
using namespace std;

class Solution
{
public:
    bool isValid(string s)
    {
        if (1 == s.size())
            return false;

        stack<char> sc;
        for (const auto& ch : s)
        {
            if (ch == '(' ||
                ch == '{' ||
                ch == '[')
                sc.push(ch);
            else
            {
                if (sc.empty())
                    return false;

                char top = sc.top();
                if ((top == '(' && ch == ')') ||
                    (top == '{' && ch == '}') ||
                    (top == '[' && ch == ']'))
                    sc.pop();
                else
                    return false;
            }
        }

        return sc.empty();
    }
};

bool isValid(char* s)
{
    int top = 0;
    char st[10000] = { 0 };

    int i = 0;
    while (s[i])
    {
        if (s[i] == '(' ||
            s[i] == '[' ||
            s[i] == '{')
            st[top++] = s[i];
        else
        {
            if (0 == top)
                return false;

            if ((st[top - 1] == '(' && s[i] == ')') ||
                (st[top - 1] == '[' && s[i] == ']') ||
                (st[top - 1] == '{' && s[i] == '}'))
                --top;
            else
                return false;
        }
        ++i;
    }

    return 0 == top;
}

void Test1(void)
{
    string s1 = "))";
    char s2[] = "))";

    cout << Solution().isValid(s1) << endl;
    cout << isValid(s2) << endl;

}

int main()
{
    Test1();


	return 0;
}